//给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 
//
// 
//
// 示例 1： 
//
// 
//输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
//输出： True
//说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。 
//
// 示例 2: 
//
// 
//输入: nums = [1,2,3,4], k = 3
//输出: false 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= len(nums) <= 16 
// 0 < nums[i] < 10000 
// 每个元素的频率在 [1,4] 范围内 
// 
// Related Topics位运算 | 记忆化搜索 | 数组 | 动态规划 | 回溯 | 状态压缩 
//
// 👍 678, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

// 698. 划分为k个相等的子集
// https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
// 和473、1723、2305类似
class PartitionToKEqualSumSubsets {
    public static void main(String[] args) {
        Solution solution = new PartitionToKEqualSumSubsets().new Solution();
         // solution.canPartitionKSubsets(new int[]{4, 3, 2, 3, 5, 2, 1}, 4);
         solution.canPartitionKSubsets(new int[]{4, 3, 2, 2, 6, 2, 1}, 4);
//        solution.canPartitionKSubsets(new int[]{1, 1, 1, 1, 2, 2, 2, 2}, 2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[] cur;  // 表示当前每个子集的和

        // DFS + 剪枝
        // https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solution/by-lcbin-92ll/
        public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum = Arrays.stream(nums).sum();
            if (sum % k != 0) {
                return false;
            }
            Arrays.sort(nums);
            int tar = sum / k;
            this.cur = new int[k];
            return backTracking(nums, nums.length - 1, tar);
        }

        public boolean backTracking(int[] nums, int start, int tar) {
            if (start < 0) return true;
            for (int i = 0; i < cur.length; i++) {
                // 第一个数放哪个桶都一样，所以就放为第一个
                if(start == nums.length - 1 && i > 0) continue;
                // 从大到小来搜索
                // 如果当前桶和上一个桶内的元素和相等，则跳过
                // 原因：如果元素和相等，那么 nums[index] 选择上一个桶和选择当前桶可以得到的结果是一致的
                if (i > 0 && cur[i] == cur[i - 1]) continue;
                cur[i] += nums[start];
                if (cur[i] <= tar && backTracking(nums, start - 1, tar)) {
                    return true;
                }
                cur[i] -= nums[start];
            }

            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
